package com.dyz.leetcode._05_sort;

public class _493_reversePairs {
    public int reversePairs(int[] nums) {

        return mergeSort(nums, 0, nums.length-1, new int[nums.length]);
    }

    private int mergeSort(int[] nums, int lo, int hi, int[] tmp){
        if(lo>=hi){
            return 0;
        }

        int mid = lo+(hi-lo)/2;
        int leftCount = mergeSort(nums, lo, mid, tmp);
        int rightCount = mergeSort(nums, mid+1, hi, tmp);
        int count = 0;

        int l = lo;
        int j = mid+1;

        while(l<=mid){
            while(j<=hi && (long)nums[l]>2*(long)nums[j]){j++;}
            count+=(j-mid-1);
            l++;
        }

        merge(nums, lo, mid, hi, tmp);
        return leftCount+ rightCount+count;
    }

    private void merge(int[] nums, int lo, int mid, int hi, int[] tmp){
        for(int i=lo; i<=hi; i++){
            tmp[i] = nums[i];
        }
        int i=lo;
        int j=mid+1;
        for(int k=lo; k<=hi;k++){
            if(i==mid+1){
                nums[k] = tmp[j];
                j++;
            }else if(j==hi+1){
                nums[k] = tmp[i];
                i++;
            }else if(tmp[i]<=tmp[j]){
                nums[k] = tmp[i];
                i++;
            }else{
                nums[k] = tmp[j];
                j++;
            }
        }
    }
}
